// 给你一个字符串 :和一个字符串列表wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出s
// 注意:不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

#include <stdio.h>
#include <stdlib.h>

int solution(char *s,char **wordDict,int m,int n){
    int *dp = (int*)malloc((m+1) * sizeof(int));
    dp[0] = 1;
    // 初始化dp
    for(int i=1;i<=m;i++){
        dp[i] = 0;
    }

    // 动态规划
    for(int i=0;i<m;i++){
        char c = s[i];
        for(int j=0;j<n;j++){
            char *word = wordDict[j];
            // 计算字符串长度
            int k = 0;
            while(word[k] != '\0'){
                k++;
            }
            
            // 状态转移
            if(i+1-k < 0){
                continue;
            }
            if(word[k-1] != c){
                continue;
            }
            // 字符串匹配
            int bool_v = 1;
            for (int w = 0; w < k; w++){
                if(word[k-1-w] != s[i-w]){
                    bool_v = 0;
                    break;
                }
            }
            if(bool_v == 1){
                dp[i+1] = dp[i+1-k];
            }
        }
    }

    return dp[m];
}


int main(){
    char s[] = "leetccode";
    char *wordDict[] = {"leet","coe","lee","co","tc","de"};
    int m = sizeof(s)/sizeof(s[0]) - 1;
    int n = sizeof(wordDict)/sizeof(wordDict[0]);
    int result = solution(s,wordDict,m,n);
    printf("%d",result);



    return 0;
}